% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{ulem}

\newcounter{task}
\newcommand{\task}{\stepcounter{task}\paragraph{Task \thetask~--~
Solution}}

\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large 2. Problem Session -- Solution\\ \vspace{0.2em}
        {\bf Secure Channels}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}


\begin{document}
\pagestyle{plain}
\header


% number of tasks are automatically generated

\task
Solutions to Task 1\\
\\
\textbf{(a) SEM-security $\Longrightarrow{}$ FtG-security}\\
\\
Solution:\\
$A$ is a FtG-security adversary. We need to construct a new adversary $B$ using $A$ to attack SEM-security. Let $O_B(.)$ be $B$'s encryption oracle, b - is a random value from  from \{0,1\}, a probability 1/2 assigned to each of $x_0$ and $x_1$. We run A to find a couple of messages, then to guess the value of a plain text (identiity function). \\\\
Algorithm $B^{O_B(.)}(select)$\\
1. Let $(x_0, x_1) \xleftarrow{} A^{O_{B}(.)}(find)$\\
2. Return $(x_0,x_1)$ - messages set M with a probability 1/2 assigned to each $x_0$ and $x_1$. \\
\\
Algorithm $B^{O_{B}(.)}(k, predict, O_2(x_b))$\\
1. Let $d \xleftarrow{} A^{O_{B}(.)}(k, guess,  O_2(x_b), s)$\\
2. Return $(f, x_d)$, where f is the identity function.\\
\\
For the advantage of $B$ we have,\\
$Adv_{B}^{sem-cpa} = Pr[Exp_{A}^{ftg-cpa-1} = 1]-Pr[Exp_{A}^{ftg-cpa-0} = 1]=Adv_{A}^{ftg-cpa}$\\
\\\\
\textbf{(b) FtG-security $\Longrightarrow{}$ SEM-security}\\
\\
Solution:\\
$A$ is a SEM-security adversary. We need to construct a new adversary $B$ using $A$ to attack FtG-security. Let $O_B(.)$ be $B$'s encryption oracle, b - a random value from \{0,1\}, a probability 1/2 assigned to each of $x_0$ and $x_1$.
We need to get a couple of messages from A, run A on the challenge and decide with the results.\\\\
Algorithm $B^{O_B(.)}(find)$\\
1. Let $(M) \xleftarrow{} A^{O_{B}(.)}(select)$, M - message distribution\\
2. Return $x_0 \xleftarrow{} M; x_1 \xleftarrow{} M$\\
\\
Algorithm $B^{O_B(.)}(guess, O_B(x_b))$\\
1. Let $(f, d) \xleftarrow{} A^{O_{B}(.)}(predict, O_B(x_b))$\\
2. If $d= f(x_b)$ then return 1; else return 0.\\
\\
For the advantage of $B$ we have,\\
$Adv_{B}^{ftg-cpa} = Pr[Exp_{A}^{sem-cpa-1} = 1]-Pr[Exp_{A}^{sem-cpa-0} = 1]=Adv_{A}^{sem-cpa}$\\
\\
\textbf{(c) LoR-security is not weaker than FtG-security (LoR-security $\Longrightarrow{}$ FtG-security)}\\
\\
Solution:\\
$A$ is an adversary of FtG-security. We need to construct a new adversary $B$ using $A$ to attack LoR-security. 
B can be implemented by A with the same winning probability simply by translating A's encryption
queries $x_i$ into $(x_i,x_i).$  If $O_B(.,.)$ is $B$'s encryption oracle, then for any string x, define $O_A(x)$ to be $O_B(x, x)$. \\\\
Algorithm $B^{O_B(. , .)}$\\
1. Let $(x_0, x_1,) \xleftarrow{} A^{O_{A}(.)}(find)$\\
2. Let $d \xleftarrow{} A^{O_{A}(.)}(guess, O_B(x_0, x_1))$\\
3. if d=0 then return 0, else return 1.\\
\\
For the advantage of $B$ we have,\\
$Adv_{B}^{LoR-cpa} = Pr[Exp_{A}^{FtG-cpa-1}=1]-Pr[Exp_{A}^{FtG-cpa-0}=1]=Adv_{A}^{FtG-cpa}$


\task
Solutions to Task 2\\
\\
Let b random from \{0,1\},\\
$K(k)$ is key generate function,\\ 
$E_k(k)$ is encryption function, \\
$D_k(k)$ is decryption function.\\
and we consider the following experiments:\\
\\
Experiment: $Exp_{(K,E,D), A_{}}^{hw-cpa-b}$\\
\\
$K \xleftarrow{R} K$\\
$(M,s) \xleftarrow{} A_{cpa}^{E_k(.)}(select)$\\
$x_0 \xleftarrow{} M; x_1 \xleftarrow{} M$\\
$y \xleftarrow{} E_k(x_b)$\\
$d \xleftarrow{} A_{cpa}^{E_k(.)}(hw(.), y, s)$\\
if $d=hw(x_b) $then return 1, else return 0.\\
\\
So the advantage of HW-security is\\
\\
$Adv_{A_cpa}^{hw-cpa}=Pr[Exp_{A}^{hw-cpa-1}=1]-Pr[Exp_{A}^{hw-cpa-0}=1]$\\
\\
\textbf{(a) SEM-security $\Longrightarrow{}$ HW-security or not}\\
\\
Solution:\\
Assume $A$ is adversary of HW-security,  and construct a new adversary $B$ using $A$ to attack SEM-security. Let $O_B(.)$ be $B$'s encryption oracle, b  - a random value from \{0,1\}\\\\
Algorithm $B^{O_B(.)}(select)$\\
1. Return $(x_0,x_1) \xleftarrow{} A^{O_{B}(.)}( select)$\\
\\
Algorithm $B^{O_{B}(.)} predict, O_B(x_b))$\\
1. Let $d \xleftarrow{} A^{O_{B}(.)}( hw(.), O_B(x_b))$\\
2. Return $(f, d)$, where f is the identity function.\\
\\
For the advantage of $B$ we have,\\
$Adv_{B}^{sem-cpa} = Pr[Exp_{A}^{hw-cpa-1}=1]-Pr[Exp_{A}^{hw-cpa-0}=1]=Adv_{A}^{hw-cpa}(k)$\\
\\
So SEM-security $\Longrightarrow{}$ HW-security\\
\\
\textbf{(b) HW-security $\Longrightarrow{}$ SEM-security or not}\\
\\
Solution:\\
Assume $A$ is adversary of SEM-security,  and construct a new adversary $B$ using $A$ to attack HW-security. Let $O_B(.)$ be $B$'s encryption oracle, b- a random value from \{0,1\}\\\\
Algorithm $B^{O_B(.)}(select)$\\
1. return  $(x_0, x_1) \xleftarrow{} A^{O_{B}(.)}(select)$\\
\\
Algorithm $B^{O_B(.)}( hw(.), O_B(x_b))$\\
1. Let $d \xleftarrow{} A^{O_{B}(.)}(guess, O_B(x_b))$\\
2. if $hw(x_b)=d$ return value 1, else return 0.\\
\\
For the advantage of $B$ we have,\\
$Adv_{B}^{hw-cpa} = Pr[Exp_{A}^{sem-cpa-1}=1]-Pr[Exp_{A}^{sem-cpa-0}=1]=Adv_{A}^{sem-cpa}$\\
\\
So HW-security $\Longrightarrow{}$ SEM-security\\
\\\\References:\\
1) \url{ http://www.cs.fsu.edu/~breno/CIS-6930/lecture_slides/class04.pdf}\\
2) \url{http://www-verimag.imag.fr/~plafourc/teaching/Presentation_M2P2009_2010/final.pdf}



% ...













\end{document}
